The Diffie-Hellman key exchange protocol allows two parties, Alice and Bob, to agree on a secret key without having exchanged any secret information beforehand! The method is based in cyclic groups, so read up on that in the mathematical prerequisites.

The protocol itself is based on the group , where is some huge prime number. The prime numbers that can be used in the Diffie-Hellman (DH) key exchange are standardised - they are public knowledge and can be found in various RFCs on the Internet. More specifically, the prime must be a safe prime, i.e. a prime such that , where is also prime.

One such prime $p$ can be found in [RFC 3526](https://www.rfc-editor.org/rfc/rfc3526#page-5) and is 4096 bits long.
Copy

Notice that since , the prime divides and so the group has an element of order and the powers of generate the group . It turns out that this group is a subgroup of . We are now ready to outline the DH key exchange.

The primes as well as the generator are public knowledge and are standardised in various RFCs.

Alice picks a random power between and , i.e. a uniform and computes . Similarly, Bob picks a uniform and computes . Alice and Bob then exchange the values and which they computed - Alice obtains from Bob and Bob obtains from Alice.

Alice now computes and Bob computes - the two parties have arrived at the same key ! Interestingly enough, any eavesdropping adversary cannot arrive at the same value by just observing the communication channel, since they do not know the secret values and which Alice and Bob picked separately for themselves.

The security of the Diffie-Hellman protocol is defined according to certain mathematical problems.

In trying to break the Diffie-Hellman key exchange, the adversary Eve is in a way trying to solve the discrete logarithm problem. The function denotes the discrete logarithm function with base and is the function that returns the power which you need to raise to in order to obtain , i.e. Eve is trying to compute . The logarithm is called discrete because it only returns integer values due to the fact that we are working with groups

The adversary $\textit{Eve}$ is given the generator $g$ as well as the order $q$ of the generated group $\langle g \rangle$ and is provided with the group element $g^x$ for some uniform, unknown, $x \leftarrow_R \mathbb{Z}_q$. Her goal is to find the value of $x$.

We say that the discrete logarithm problem is *hard relative to* $\langle g \rangle$ if no matter what Eve does, the probability that she can find $x$ is negligible, i.e.

$$\Pr_{x\leftarrow_R \mathbb{Z}_q}[\textit{Eve}(g, q, g^x) = x] \le \textit{negl}(\cdot)$$
Copy

It should be obvious that the computational difficulty of the discrete logarithm largely depends on the group itself and so not every group yields a secure Diffie-Hellman key exchange.

There are two additional problems which are similar to the discrete logarithm problem and are known to be related but not equivalent to the each other.

The adversary $\textit{Eve}$ is given the generator $g$ as well as the order $q$ of the generated group $\langle g \rangle$ and is provided with two group elements $g^a$ and $g^b$ for some uniform, unknown, $a,b \leftarrow_R \mathbb{Z}_q$. Her goal is to then find the value of $g^{ab}$.

We say that the computational diffie-hellman problem is *hard relative to* $\langle g \rangle$ if, no matter what Eve does, the probability that she can find $g^{ab}$ is negligible, i.e.

$$\Pr_{a,b \leftarrow_R \mathbb{Z}_q}[\textit{Eve}(g, q, g^a, g^b) = g^{ab}] \le \textit{negl}(\cdot)$$
Copy

The CDH problem is essentially an exact description of the Diffie-Hellman scenario. Eve can observe the communication between Alice and Bob and is thus able to obtain the values and . However, Alice and Bob ultimately end up using the value as a key and so Eve has to find a way to compute it using only and .

The second problem is related to the CDH problem but the two problems are not known to be equivalent.

The adversary $\textit{Eve}$ knows the cyclic group $\mathbb{G}$, one of its generators $g$ and its order $q$. She is given two group elements $g^{\alpha}, g^{\beta}$ which are generated by $g$ for some uniform, unknown to Eve, powers $\alpha, \beta \leftarrow_R \mathbb{Z}_q$. Finally, Eve is either given a third such element $g^{\gamma}$ generated by some uniform unknown $\gamma \leftarrow_R \mathbb{Z}_q$ or she is given the element $g^{\alpha\beta}$. Eve's goal is to then determine if she has $g^{\alpha\beta}$ or $g^{\gamma}$.

We say that the DDH problem is *hard relative to* $\mathbb{G}$ if no matter what Eve does, the probability that she achieves her goal is negligible, i.e.

$$\left|\Pr[\textit{Eve}(\mathbb{G}, g, q, g^{\alpha}, g^{\beta}, g^{\gamma}) = 1] - \Pr[\textit{Eve}(\mathbb{G}, g, q, g^{\alpha}, g^{\beta}, g^{\alpha\beta}) = 1] \right| \le \textit{negl}(\cdot)$$
Copy

If the CDH problem is easy relative to some group, then so is the DDH problem.